#
# @lc app=leetcode.cn id=16 lang=python3
#
# [16] 最接近的三数之和
#

"""
本题思路和 [15.三数之和] 一致，在最外层循环枚举 i ，在内层循环使用双指针寻找符合题意的 j, k
不同的是，本题需要寻找与 target 接近的三数之和，所以需要增加一个 minDiff 变量用来存储三数之和与 target 的差，当发现更小的三数之和时来更新该变量

"""

# @lc code=start
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        n = len(nums)
        nums.sort()
        res = 0
        minDiff = inf

        for i in range(n-2):
            x = nums[i]

            if i and nums[i-1] == x: continue

            s = x + nums[i+1] + nums[i+2]
            if s > target:
                if s - target < minDiff:
                    res = s
                break

            s = x + nums[-2] + nums[-1]
            if s < target:
                if target - s < minDiff:
                    minDiff = target - s
                    res = s
                continue

            j = i + 1
            k = n - 1
            
            while j < k:
                s = x + nums[j] + nums[k]
                if s == target: return s
                elif s > target: 
                    if s - target < minDiff:
                        minDiff = s - target
                        res = s
                    k -= 1        
                else:
                    if target - s < minDiff: 
                        minDiff = target - s
                        res = s
                    j += 1

        
        return res
# @lc code=end

